1. Field of the Invention
The present invention relates to a multi-way set associative cache system having at least two sets, each set having a plurality of cache lines, wherein blocks of a lower memory of the cache correspond to a cache line of each set in an overlapping manner, so that the hit ratio of the cache can be increased.
2. Description of the Related Art
Conventionally, there are various cache systems with various cache line structures.
First, a direct mapped cache system will be described as an example of basic cache systems.
As shown in FIG. 1, a direct mapped cache system comprises a cache data memory 2 and a cache tag memory 3. A memory 1 is provided as a lower memory of this cache system. The term "lower" indicates that the memory is provided at a distance position from a processor. That is, if this cache system is provided for a main memory, the memory 1 is the main memory. The memory 1 has a plurality of blocks. The size of data stored in each block is called "a line size", where its unit is "a byte". With equal line sizes the blocks of the memory 1, all blocks contain the same number of bytes. Cache lines are provided accordingly for use of storing copies in data stored in blocks.
For example, a cache line 21 of the cache data memory 2 corresponds to blocks 11 to 14 of the lower memory 1, as indicated by arrows h1 to h4 in FIG. 1. In this case, the cache line 21 is capable of storing data stored in one of the blocks 11 to 14. For convenience of explanation, it is assumed that the cache line 21 stores data of the lower memory block 12.
The cache tag memory 3 has a plurality of cache tags respectively corresponding to the cache lines. Each cache tag represents the block which stores data of the corresponding cache line. More specifically, each cache tag has tag data representing an address of the block in which data stored in the corresponding cache line is stored. For example, a cache tag 31, corresponding to the cache data memory 21, has tag data representing the address of the lower memory block 12.
If the cache receives a data input/output request (access) from a CPU (central processing unit) of a processor (not indicated), the tag data is used to judge whether requested data is stored in the cache data memory.
As is well known, a hit occurs when a cache receives a data input/output request, if the data has been stored in the cache and can be immediately read out in reply to the request. A "miss" or "miss hit" occurs when the data has not been stored in the cache and data must be read from the lower memory and loaded in the cache. If a miss hit occurs, the data input/output efficiency is reduced (the process rate is lowered) since the requested data must be loaded in the cache. Hence, market demand for a cache system, having a low miss hit ratio (i.e., a high hit ratio), has been increasing.
With reference to FIG. 1, the cache line 21 stores data of the lower memory block 12, and not of the lower memory block 13, and a miss hit will thus occur if data of the block 13 is requested.
In this case, the data of the block 13 is loaded into the cache line 21, and the data of the block 12, which has been stored in the cache line 21, is lost. If the data of the block 12 is requested after the data of the block 13 is loaded in the cache line 21, a miss hit will occur again.
As described above, each of the lower memory blocks 11 to 14 in the direct mapped cache system, correspond to only one cache line of the cache data memory 2. Thus, if an input/output request for data in the lower memory blocks 11 to 14 is generated frequently, the miss hit ratio (cache miss ratio) of the entire cache system will inevitably be increased.
To reduce the miss hit ratio, a so-called multi-way set associative cache system has been proposed.
A multi-way set associative cache system, as shown in FIG. 2, has a lower memory 1, a plurality of cache data memories 2a and 2b and a plurality of cache tag memories 3a and 3b. In other words, the multi-way set associative cache system has a plurality of sets of cache data memories and cache tag memories, whereas the direct mapped cache system described above has only one set.
More specifically, the direct mapped cache system has one set (the cache data memory 2 and the cache tag memory 3), whereas the multi-way set associative cache system has a plurality of sets, i.e., a set 4a (the cache data memory 2a and the cache tag memory 3a) and a set 4b (the cache data memory 2b and the cache tag memory 3b). Since the example shown in FIG. 2 has two sets, it is called a 2-way set associative cache system.
In FIG. 2, the blocks 11 to 14 of the lower memory 1 correspond not only to a cache line 21a (a cache tag 31a) of the cache data memory 2a, as indicated by arrows a1 to a4, but also to a cache line 21b (a cache tag 31b) of the cache data memory 2b, as indicated by arrows b1 to b4. In the direct mapped cache system (FIG. 1), the data of the block 13 cannot be stored in the cache line 21 when the data of the block 12 is stored in the cache line 21. On the other hand, since the 2-way set associative cache system shown in FIG. 2 has two sets 4a and 4b, it is possible that the blocks 11 to 14 correspond to both the cache lines 21a and 21b. Hence, for example, data of the blocks 12 and 13 can be individually stored in the cache lines 21a and 21b, so that the miss hit ratio can be lowered.
It is thus evident that the miss hit ratio is lowered as the more the number of cache memory sets of the same structure is increased. This fact has been known.
However, in the conventional cache system, even if the number of cache memory sets of the same structure is increased, the capacity of the memories required for constituting the system is increased in proportion to the number of sets, but the miss hit ratio cannot be lowered in accordance with the number of sets.